#include <vector>
using namespace std;
#include <cstdlib>
#include <ctime>


//version 1   使用三路划分 + 随机选取key  快排
class Solution {
private:
    void myqsort(int left, int right, vector<int>& arr){
        if(left >= right) return;
        //1.先随机选取一个key（千万不要选keyi，也就是坐标）
        //因为坐标对应的值可能会变！使用坐标就出问题了！
        int key = arr[(rand() % (right - left + 1)) + left];
        int begin = left - 1, end = right + 1, i = left;
        while(i < end){
            if(arr[i] < key) std::swap(arr[++begin], arr[i++]);
            else if(arr[i] == key) ++i;
            else std::swap(arr[--end], arr[i]);
        }
        //排完一遍序
        //[left, begin] < keyi   [begin + 1, end - 1] == keyi  [end, right] > keyi
        myqsort(left, begin, arr);
        myqsort(end, right, arr);
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned int)time(nullptr));
        myqsort(0, nums.size() - 1, nums);
        return nums;
    }
};



//version 2  归并递归
class Solution {
private:
    void MergeSort(vector<int>& tmp, vector<int>& arr, int left, int right){
        if(left >= right) return;

        int mid = (left + right) / 2;
        //int mid = left + (right - left) / 2;
        //[left, mid] [mid + 1, right]
        MergeSort(tmp, arr, left, mid);
        MergeSort(tmp, arr, mid + 1, right);

        //左右两个子区间都已经归并排序好了！合并成新的数组
        int begin1 = left, end1 = mid, begin2 = mid + 1, end2 = right, i = left;
        while(begin1 <= end1 && begin2 <= end2){
            if(arr[begin1] <= arr[begin2]) tmp[i++] = arr[begin1++];
            else tmp[i++] = arr[begin2++];
        }
        while(begin1 <= end1) tmp[i++] = arr[begin1++];
        while(begin2 <= end2) tmp[i++] = arr[begin2++];

        //把缓冲数组内的内容拷贝给tmp
        for(int j = left; j < i; ++j) arr[j] = tmp[j];
    }    
public:
    vector<int> sortArray(vector<int>& nums) {
        vector<int> tmp(nums.size());
        MergeSort(tmp, nums, 0, nums.size() - 1);
        return nums;
    }
};